import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 *  Resource：https://leetcode-cn.com/problems/valid-parentheses/
 *  解题思路：1.如果来的是右括号，则取栈顶元素，判断是否是右括号对应的左括号，如果是，则继续，不是，则不匹配，直接返回false;
 *  2.如果来的是左括号，将其压栈
 * @author junzhongliu
 * @date 2018/12/21 13:53
 */
public class ValidParentheses {

    public static void main(String[] args) {
        String s = "]";
        System.out.println(isValid(s));
    }

    public static boolean isValid(String s) {
        if(s==null || s.length()==0 || s==""){
            return true;
        }
        Map<Character,Character> mappings = new HashMap<>();
        mappings.put(')','(');
        mappings.put(']','[');
        mappings.put('}','{');

        Stack<Character> stack = new Stack<>();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(mappings.containsKey(c)){
                //key中存在这个元素
                if(stack.empty()){
                    return false;
                }
                //取栈顶元素，如果不等于key存储的那个对称的value，则不符合
                Character pop = stack.pop();
                if(!pop.equals(mappings.get(c))){
                    return false;
                }
            }else{
                //hash中不存在这个key，将其压栈
                stack.push(c);
            }
        }
        return stack.empty();
    }

}
